package com.squirrel.michale;

import java.util.Arrays;

/**
 * 给你一个 n 个节点的带权无向图，节点编号为 0 到 n - 1 。
 *
 * 给你一个整数 n 和一个数组 edges ，其中 edges[i] = [ui, vi, wi] 表示节点 ui 和 vi 之间有一条权值为 wi 的无向边。
 *
 * 在图中，一趟旅途包含一系列节点和边。旅途开始和结束点都是图中的节点，且图中存在连接旅途中相邻节点的边。注意，一趟旅途可能访问同一条边或者同一个节点多次。
 *
 * 如果旅途开始于节点 u ，结束于节点 v ，我们定义这一趟旅途的 代价 是经过的边权按位与 AND 的结果。换句话说，如果经过的边对应的边权为 w0, w1, w2, ..., wk ，那么代价为w0 & w1 & w2 & ... & wk ，其中 & 表示按位与 AND 操作。
 *
 * 给你一个二维数组 query ，其中 query[i] = [si, ti] 。对于每一个查询，你需要找出从节点开始 si ，在节点 ti 处结束的旅途的最小代价。如果不存在这样的旅途，答案为 -1 。
 *
 * 返回数组 answer ，其中 answer[i] 表示对于查询 i 的 最小 旅途代价。
 *
 *
 *
 * 示例 1：
 *
 * 输入：n = 5, edges = [[0,1,7],[1,3,7],[1,2,1]], query = [[0,3],[3,4]]
 *
 * 输出：[1,-1]
 *
 * 解释：
 *
 *
 *
 * 第一个查询想要得到代价为 1 的旅途，我们依次访问：0->1（边权为 7 ）1->2 （边权为 1 ）2->1（边权为 1 ）1->3 （边权为 7 ）。
 *
 * 第二个查询中，无法从节点 3 到节点 4 ，所以答案为 -1 。
 *
 * 示例 2：
 *
 * 输入：n = 3, edges = [[0,2,7],[0,1,15],[1,2,6],[1,2,1]], query = [[1,2]]
 *
 * 输出：[0]
 *
 * 解释：
 *
 *
 *
 * 第一个查询想要得到代价为 0 的旅途，我们依次访问：1->2（边权为 1 ），2->1（边权 为 6 ），1->2（边权为 1 ）。
 *
 * https://www.bilibili.com/video/BV1ut421H7Wv/?vd_source=dd94464bac13f791ea6a2e385d28295a  第四题
 *
 */
public class Day20240413_LeetCode003108_03 {

    public int[] minimumCost(int n, int[][] edges, int[][] query) {
        int[] parent = new int[n];
        int[] size = new int[n];

        int sets;
        int[] weight = new int[n];
        int[] andBit = new int[n];

        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }

        Arrays.fill(weight,-1);
        Arrays.fill(andBit,-1);
        for (int i = 0; i < edges.length; i++) {
            int[] edge = edges[i];
            int x = find(edge[0], parent);
            int y = find(edge[1], parent);
            weight[i] = edge[2];

            andBit[y] &= edge[2];

            if (x != y) {
                andBit[y] &= andBit[x];
                parent[x] = y;
            }
        }

        int[] ans = new int[query.length];

        for (int i = 0; i < query.length; i++) {
            int s = query[i][0], t = query[i][1];
            ans[i] = find(s, parent) != find(t, parent) ? -1 : andBit[find(s, parent)];
        }
        return ans;
    }




    // 从i开始一直往上，往上到不能再往上，代表节点，返回
    // 这个过程要做路径压缩
    private int find(int x, int[] parent) {
        int[] help = new int[parent.length];
        int hi = 0;
        while (x != parent[x]) {
            help[hi++] = x;
            x = parent[x];
        }
        for (hi--; hi >= 0; hi--) {
            parent[help[hi]] = x;
        }
        return x;
    }


    public static void main(String[] args) {
       // n = 5, edges = [[0,1,7],[1,3,7],[1,2,1]], query = [[0,3],[3,4]]
        int n = 5;
        int[][] edges = new int[][] {{0,1,7},{1,3,7},{1,2,1}};
        int[][] query = new int[][]{{0, 3}, {3, 4}};

        Day20240413_LeetCode003108_03 day20240413LeetCode00310803 = new Day20240413_LeetCode003108_03();
        int[] ints = day20240413LeetCode00310803.minimumCost(n, edges, query);
        System.out.println(Arrays.toString(ints));


    }



//    作者：灵茶山艾府
//    链接：https://leetcode.cn/problems/minimum-cost-walk-in-weighted-graph/solutions/2727290/xian-xing-zuo-fa-dfspythonjavacgo-by-end-i0gg/
//    来源：力扣（LeetCode）
//    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。


    public static class UnionFind {
        // parent[i] = k ： i的父亲是k
        private int[] parent;
        // size[i] = k ： 如果i是代表节点，size[i]才有意义，否则无意义
        // i所在的集合大小是多少
        private int[] size;
        // 辅助结构
        private int[] help;
        // 一共有多少个集合
        private int sets;

        public UnionFind(int N) {
            parent = new int[N];
            size = new int[N];
            help = new int[N];
            sets = N;
            for (int i = 0; i < N; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        // 从i开始一直往上，往上到不能再往上，代表节点，返回
        // 这个过程要做路径压缩
        private int find(int i) {
            int hi = 0;
            while (i != parent[i]) {
                help[hi++] = i;
                i = parent[i];
            }
            for (hi--; hi >= 0; hi--) {
                parent[help[hi]] = i;
            }
            return i;
        }

        public void union(int i, int j) {
            int f1 = find(i);
            int f2 = find(j);
            if (f1 != f2) {
                if (size[f1] >= size[f2]) {
                    size[f1] += size[f2];
                    parent[f2] = f1;
                } else {
                    size[f2] += size[f1];
                    parent[f1] = f2;
                }
                sets--;
            }
        }

        public int sets() {
            return sets;
        }
    }





}
